<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /* 
      四数之和其实和三数之和很相似，就是四指针而已。
      重点：第二个指针j跳过的时候，必须额外携带一个条件j>i+1。因为 1  1  1  4  5
      i==0  j=i+1 nums[j]也是1 这种情况nums[j]==nums[j-1]，但是nums[j-1]是nums[i],是满足的，无需跳  
      而当j==2的时候，这时候nums[j]==nums[j-1]&&j>i+1可以跳了
      
      */
      var fourSum = function (nums, target) {
        let result = []
        nums.sort((a, b) => a - b)
        for (let i = 0; i < nums.length; i++) {
          if (nums[i] == nums[i - 1]) continue
          for (let j = i + 1; j < nums.length; j++) {
            if (nums[j] == nums[j - 1] && j > i + 1) continue
            let left = j + 1
            let right = nums.length - 1
            while (left < right) {
              let sum = nums[i] + nums[j] + nums[left] + nums[right]
              if (sum < target) {
                left++
              } else if (sum > target) {
                right--
              } else {
                while (nums[left] == nums[left + 1]) {
                  left++
                }
                while (nums[right] == nums[right - 1]) {
                  right--
                }
                result.push([nums[i], nums[j], nums[left], nums[right]])
                left++
                right--
              }
            }
          }
        }
        return result
      }
    </script>
  </body>
</html>
